package dataStructure.Heap;

import java.util.PriorityQueue;

//TODO TODO TODO
//大根堆
public class Heap<V> {

    private int len;
    private int cap;
    private Object[] arr;

    public Heap(int size) {
        cap = size;
        arr = new Object[size];
    }

    public V peek() {
        return len == 0 ? null : (V) arr[0];
    }

    public void add(V v) throws Exception {
        if (len == cap) {
            throw new Exception();
        }
        arr[len] = v;
        siftUp(len, v);
        len++;
    }

    private void heapify() {
        for (int i = len-1; i >= 0; i--) {
            siftDown(i, (V) arr[i]);
        }
    }

    private void siftUp(int idx, V v) {
        Comparable<? super V> parent = (Comparable<? super V>) arr[(idx-1)/2];
        while (parent.compareTo(v) > 0) {
            arr[(idx-1)/2] = v;
            arr[idx] = parent;
            idx = (idx-1)/2;
            parent = (Comparable<? super V>) arr[(idx-1)/2];
        }
    }

    private void siftDown(int idx, V v) {
        int child =
                ((Comparable<? super V>) arr[idx*2+1]).compareTo((V) arr[idx*2+2])
                        <= 0 ? idx*2+1 : idx*2+2;

        while (((Comparable<? super V>)arr[child]).compareTo(v) < 0) {
            Object tmp = arr[child];
            arr[child] = v;
            arr[idx] = tmp;
            idx = child;
            child =
                    ((Comparable<? super V>) arr[idx*2+1]).compareTo((V) arr[idx*2+2])
                            <= 0 ? idx*2+1 : idx*2+2;
        }
    }

    public V poll() {
        V result = (V) arr[0];
        len--;
        arr[0] = arr[len];
        siftDown(0, (V) arr[0]);
        return result;
    }

    public static void main(String[] args) throws Exception {
        Heap<String> stringHeap = new Heap<>(10);
        stringHeap.add("a");
        stringHeap.add("c");
        stringHeap.add("q");
        stringHeap.add("w");
        stringHeap.add("z");
        stringHeap.add("a");
        stringHeap.add("p");
        stringHeap.add("p");
        stringHeap.add("p");
        stringHeap.add("p");

        for (Object s : stringHeap.arr) {
            System.out.printf("%s ", s);
        }
        System.out.println();

        PriorityQueue<String> queue = new PriorityQueue<>(10);
        queue.add("a");
        queue.add("c");
        queue.add("q");
        queue.add("w");
        queue.add("z");
        queue.add("a");
        queue.add("p");
        queue.add("p");
        queue.add("p");
        queue.add("p");
        System.out.println(queue);
    }

}

class HeapSort {
    public static void heapSort(int[] arr) {
        heapify(arr);
        int tmp;
        int child;
        for (int i = 0; i < arr.length; i++) {
            tmp = arr[0];
            arr[0] = arr[arr.length-1];

            //siftDown
            if (i*2+1 >= arr.length)
                continue;
            else if (i*2+2 >= arr.length)
                child = i*2+1;
            else
                child = arr[i*2+1] > arr[i*2+2] ? i*2+2 : i*2+1;
            while (arr[child] > arr[i]) {
                tmp = arr[child];
                arr[child] = arr[i];
                arr[i] = tmp;
                i = child;
                if (i*2+2 >= arr.length)
                    break;
                child = arr[i*2+1] > arr[i*2+2] ? i*2+2 : i*2+1;
            }

            arr[arr.length-1-i] = tmp;
        }
    }

    private static void heapify(int[] arr) {
        int child;
        int tmp;
        for (int i = arr.length-1; i >= 0; i--) {
            if (i*2+1 >= arr.length)
                continue;
            else if (i*2+2 >= arr.length)
                child = i*2+1;
            else
                child = arr[i*2+1] > arr[i*2+2] ? i*2+2 : i*2+1;

            while (arr[child] > arr[i]) {
                tmp = arr[child];
                arr[child] = arr[i];
                arr[i] = tmp;
                i = child;
                if (i*2+2 >= arr.length)
                    break;
                child = arr[i*2+1] > arr[i*2+2] ? i*2+2 : i*2+1;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {3,1,65,3,4,2,6,2,36,33,11,9};
        heapSort(arr);
        for (Object s : arr) {
            System.out.printf("%s ", s);
        }
        System.out.println();
    }
}
